package 单周赛.history;

import util.ListNode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.TreeMap;

/**
 *
 */
public class 第358场单周赛 {

    public static void main(String[] args) {

    }

    /**
     * 模拟
     */
    public int maxSum(int[] nums) {
        int ans = -1;
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (getMaxB(nums[i]) == getMaxB(nums[j])) {
                    ans = Math.max(ans, nums[i] + nums[j]);
                }
            }
        }
        return ans;
    }

    private int getMaxB(int num) {
        int n = 0;
        while (num > 0) {
            n = Math.max(n, num % 10);
            num /= 10;
        }
        return n;
    }

    /**
     * 链表反转+数学
     */
    public ListNode doubleIt(ListNode head) {
        ListNode node = reverseList(head);
        List<Integer> list = new ArrayList<>();
        int pre = 0;
        while (node != null) {
            int cur = node.val * 2 + pre;
            list.add(cur % 10);
            pre = cur / 10;
            node = node.next;
        }
        if (pre != 0) {
            list.add(pre);
        }
        ListNode vir = new ListNode(-1);

        ListNode tempNode = vir;
        for (int i = list.size() - 1; i >= 0; i--) {
            tempNode.next = new ListNode(list.get(i));
            tempNode = tempNode.next;
        }
        return vir.next;
    }

    public static ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            //保存下一个节点
            ListNode next = cur.next;
            //指针指向下一个节点改为指向前一个节点
            cur.next = pre;
            //pre，cur步进1步
            pre = cur;
            cur = next;
        }
        return pre;
    }

    /**
     * 排序+模拟（超时！！！）
     */
    public int minAbsoluteDifference(List<Integer> nums, int x) {
        if (x == 0) return 0;

        int ans = Integer.MAX_VALUE;
        int[][] arrs = new int[nums.size()][2];
        for (int i = 0; i < nums.size(); i++) {
            arrs[i] = new int[]{i, nums.get(i)};
        }
        Arrays.sort(arrs, (a, b) -> a[1] - b[1]);

        for (int i = 0; i < arrs.length; i++) {
            for (int j = i + 1; j < arrs.length; j++) {
                if (Math.abs(arrs[i][0] - arrs[j][0]) >= x) {
                    ans = Math.min(ans, arrs[j][1] - arrs[i][1]);
                    break;
                }
            }
        }
        return ans;
    }

    /**
     * 模拟（超时！！！）
     */
    public int minAbsoluteDifference2(List<Integer> nums, int x) {
        int ans = Integer.MAX_VALUE;

        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + x; j < nums.size(); j++) {
                ans = Math.min(ans, Math.abs(nums.get(i) - nums.get(j)));
            }
        }
        return ans;
    }

    /**
     * 滑动窗口+平衡树+贪心
     * 例如 [4,3,2,4] ，对于 nums[0] = 4 来说，得到 [0+x,n-1] 中
     * > 4 的最小值，和 < 4 的最大值，或者 = 4 值，就能算出 nums[0]
     * 的最小绝对值差值，对于 nums[1]，得到 [1+x,n-1] 中...就能得出，
     * 快速找到 [idx+x,n-1] 的大于，小于，等于某个值，可以用平衡树
     * 找到，对于 idx 0 --> 1，平衡树中元素[0+x,n-1] --> [1+x,n-1]
     * 可能需要移除 nums[0+idx] 的元素，nums[idx+x] 如果是数组中
     * 最后出现的索引，那么需要从平衡树中移除，对于平衡树中重复出现的
     * 数字，贪心的保留最大索引就行
     */
    public int minAbsoluteDifference3(List<Integer> nums, int x) {
        int ans = Integer.MAX_VALUE;
        TreeMap<Integer, Integer> treeMap = new TreeMap<>();
        for (int i = x; i < nums.size(); i++) {
            treeMap.put(nums.get(i), i);
        }
        for (int i = 0; i < nums.size(); i++) {
            Integer num = nums.get(i);
            if (treeMap.containsKey(num)) {
                return 0;
            }
            Integer higher = treeMap.higherKey(num);
            if (higher != null) {
                ans = Math.min(ans, higher - num);
            }
            Integer lower = treeMap.lowerKey(num);
            if (lower != null) {
                ans = Math.min(ans, num - lower);
            }
            if (i + x >= nums.size()) break;
            if (treeMap.get(nums.get(i + x)) == (i + x)) {
                treeMap.remove(nums.get(i + x));
            }
        }
        return ans;
    }

}
